package com.bwt.huffmanCode;

import java.io.*;
import java.util.*;

public class HuffmanCode {
	public static void main(String[] args) {
		// 测试压缩文件
		String srcFile = "C:\\Users\\15459\\Desktop\\zipTest.png";
		String dstFile = "C:\\Users\\15459\\Desktop\\zipTest.zip";
		zipFile(srcFile, dstFile);
		System.out.println("压缩成功");

		// 测试解压文件
		String zipFile = "C:\\Users\\15459\\Desktop\\zipTest.zip";
		String dstFile2 = "C:\\Users\\15459\\Desktop\\2.png";
		unZipFile(zipFile, dstFile2);
		System.out.println("解压成功");

     /*   //压缩解压字符串
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println(contentBytes.length);//40

        byte[] huffmanCodeBytes = huffmanZip(contentBytes);
        System.out.println("huffmanCodeBytes == " + Arrays.toString(huffmanCodeBytes)); //17
        //1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
        byte[] sourceBytes = decode(huffmanCodes, huffmanCodeBytes, getHuffmanCodeStrLength(contentBytes,huffmanCodes));
        //原来的字符串:i like like like java do you like a java
        System.out.println("原来的字符串:" + new String(sourceBytes));*/


        /*//封装node节点
        List<Node> nodes = getNodes(contentBytes);
        System.out.println(nodes);
        //创建赫夫曼树
        Node root = createHuffmanTree(nodes);
        root.preOrder();
        //获取对应节点的赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(root);
        System.out.println("生成的赫夫曼编码表:"+huffmanCodes);
        //获取压缩后的字节数组
        byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
        //huffmanCodeBytes == [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
        System.out.println("huffmanCodeBytes == "+Arrays.toString(huffmanCodeBytes));//17个字节*/
	}


	/**
	 * 文件解压
	 *
	 * @param zipFile
	 * @param dstFile
	 */
	public static void unZipFile(String zipFile, String dstFile) {
		// 定义文件输入流
		InputStream is = null;
		// 定义一个对象输入流
		ObjectInputStream ois = null;
		// 文件输出流
		OutputStream os = null;
		try {
			// 创建文件输入流
			is = new FileInputStream(zipFile);
			// 创建一个和is 关联的对象输入流
			ois = new ObjectInputStream(is);
			// 读取byte[]
			byte[] huffmanBytes = (byte[]) ois.readObject();
			Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
			int len = (int) ois.readObject();
			// 解码
			byte[] bytes = decode(huffmanCodes, huffmanBytes, len);
			// 将bytes写入到目标文件
			os = new FileOutputStream(dstFile);
			// 写数据到文件中
			os.write(bytes);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				os.close();
				ois.close();
				is.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}

	/**
	 * 文件压缩
	 *
	 * @param srcFile 希望压缩的文件全路径
	 * @param dstFile 压缩后的文件目录
	 */
	public static void zipFile(String srcFile, String dstFile) {
		FileInputStream is = null;
		FileOutputStream os = null;
		ObjectOutputStream oos = null;
		// 创建文件输入流
		try {
			is = new FileInputStream(srcFile);
			// 创建一个和源文件大小的一样的byte[]
			byte[] b = new byte[is.available()];
			// 读取文件
			is.read(b);
			// 获取文件对应的赫夫曼编码表
			// 直接对源文件压缩
			byte[] huffmanBytes = huffmanZip(b);
			// 创建文件输出流
			os = new FileOutputStream(dstFile);
			// 创建一个和文件输出流关联的ObjectOutputStream
			oos = new ObjectOutputStream(os);
			// 把赫夫曼编码后的字节数组写入压缩文件
			oos.writeObject(huffmanBytes);
			// 这里以对象流的方式写入 赫夫曼编码, 是为了以后我们恢复源文件时使用
			// 注意! 一定要把赫夫曼编码 写入压缩文件
			oos.writeObject(huffmanCodes);

			// 写入原始字节数组的转赫夫曼编码后的二进制数组的长度
			oos.writeObject(getHuffmanCodeStrLength(b, huffmanCodes));
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				is.close();
				os.close();
				oos.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}


	/**
	 * 完成数据的解压
	 * 思路
	 * 1. 将huffmanCodeBytes == [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
	 * 重新转成赫夫曼编码对应的二进制字符串"1010100......"
	 * 2. 赫夫曼编码对应的二进制字符串 => 对照赫夫曼编码 =>  "i like like like java do you like a java"
	 */

	/**
	 * @param huffmanCodes       赫夫曼编码表map
	 * @param huffmanBytes       赫夫曼编码得到的字节数组
	 * @param huffmanCodesStrLen 赫夫曼编码对应的二进制字符串的长度
	 * @return 原来的字符串对应的数组
	 */
	private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes, int huffmanCodesStrLen) {
		// 1. 先得到huffmanBytes对应的二进制的字符串 1010100......
		StringBuilder stringBuilder = new StringBuilder();
		// 将byte数组转成二进制的字符串
		for (int i = 0; i < huffmanBytes.length - 1; i++) {
			// 判断是否被8整除, 如果整除就不用判断最后一个数据, 全部需要补位截取
			stringBuilder.append(byteToBitString(true, huffmanBytes[i]));
		}
		byte b = huffmanBytes[huffmanBytes.length - 1];
		String lastByteStr = byteToBitString(false, b);

		// 如果长度相等，那正好。拼接上去
		if (stringBuilder.length() + lastByteStr.length() == huffmanCodesStrLen) {
			stringBuilder.append(lastByteStr);
		} else {
			// 如果长度不够，那就先补0，直到总长度相等，再拼接
			while (stringBuilder.length() + lastByteStr.length() < huffmanCodesStrLen) {
				stringBuilder.append(0);
			}
			stringBuilder.append(lastByteStr);
		}

		// System.out.println("解码后的哈夫曼编码字符串为：" + stringBuilder.toString() + "长度为："+ stringBuilder.length());
		// 把字符串按照指定的赫夫曼编码进行解码
		//  把赫夫曼编码表进行调换, 因为反向查询 a->100 , 100->a
		Map<String, Byte> map = new HashMap<>();
		for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
			map.put(entry.getValue(), entry.getKey());
		}
		// 创建一个集合 ,存放byte
		List<Byte> list = new ArrayList<>();
		for (int i = 0; i < stringBuilder.length(); ) {
			int count = 1;// 小的计数器
			boolean flag2 = true;
			String subStr = null;
			while (flag2 && (i + count) <= stringBuilder.length()) {
				// 取出一个 '1'|| '0'
				subStr = stringBuilder.substring(i, i + count);// i不动, 让count移动,直到匹配到一个字符
				if (map.containsKey(subStr)) {
					flag2 = false;
				} else {
					count++;
				}
			}
			list.add(map.get(subStr));
			i += count;// i 直接移动到count

         /*   int j = i + 1;
            while (map.get(stringBuilder.substring(i, j)) == null) {
                j++;
            }
            list.add(map.get(stringBuilder.substring(i, j)));
            i = j;*/

		}
		// for循环结束后, list中就存放了所有的字符 "i like like like java do you like a java"
		// 把list中的数据放入byte[]返回
		//[105, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97, 32, 100, 111, 32, 121, 111, 117, 32, 108, 105, 107, 101, 32, 97, 32, 106, 97, 118, 97]
		// System.out.println(list);
		byte[] bt = new byte[list.size()];
		for (int i = 0; i < bt.length; i++) {
			bt[i] = list.get(i);
		}
		return bt;
	}

	public static int getHuffmanCodeStrLength(byte[] bytes, Map<Byte, String> huffmanCodes) {

		StringBuilder stringBuilder = new StringBuilder();
		// 遍历bytes数组
		for (byte b : bytes) {
			stringBuilder.append(huffmanCodes.get(b));
		}
		return stringBuilder.length();
	}

	//完成数据的解压
	//思路
	//1.将hfCoBytes[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
	//  重写先转成赫夫曼编码对应的二进制的字符串 "1010100010111..."
	//2.赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码  =》 "i like like like java do you like a java"

	/**
	 * 将一个byte 转成一个二进制的字符串, 如果看不懂,可以参考我的笔记:Java基础二进制的原码,反码,补码
	 * @param b 传入的 byte
	 * @param flag 标志是否需要补高位如果是true ,表示需要补高位,如果是false表示不补, 如果是最后一个字节,无需补高位
	 * @return 是该b 对应的二进制的字符串(注意是按补码返回)
	 */
	private static String byteToBitString(boolean flag, byte b) {
		int temp = b; // 将b 转成int
		// 如果是正数还需要补高位
		if (flag) {
			temp |= 256;
		}
		String str = Integer.toBinaryString(temp); // 返回的是temp的二进制的补码
		if (flag || temp < 0) {
			return str.substring(str.length() - 8);
		} else {
			return str;
		}
	}

	/**
	 * 压缩
	 *
	 * @param bytes 原始字符串对应的字节数组
	 * @return 经过赫夫曼编码压缩后的字节数组
	 */
	public static byte[] huffmanZip(byte[] bytes) {
		List<Node> nodes = getNodes(bytes);
		// 创建赫夫曼树
		Node root = createHuffmanTree(nodes);
		// 对应的赫夫曼编码
		Map<Byte, String> huffmanCodes = getCodes(root);
		// 返回压缩后的赫夫曼编码字节数组
		return zip(bytes, huffmanCodes);
	}

	// 将字符串对应的byte[] 数组,通过生成的赫夫曼编码表, 返回一个赫夫曼编码压缩后的byte[] 数组
	/**
	 * 举例: String content = "i like like like java do you like a java";
	 * =》 byte[] contentBytes = content.getBytes();
	 *
	 * 返回的是字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
	 * => 对应的 byte[] hfCodeBytes ,即 8位数字对应一个 byte,放入到 hfCodeBytes
	 *
	 * hfCodeBytes[0] =  10101000(补码)
	 * => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
	 * 10101000(补码)
	 * 10101000 - 1  => 10100111(反码) => 补码-1 就是反码
	 * 10100111(反码) 除去符号位 剩余全部取反就是原码
	 *
	 * hfCodeBytes[1] = -88
	 *
	 * @param bytes        这是原始的字符串对应的字节数组
	 * @param huffmanCodes 生成的huffman编码map
	 * @return 返回赫夫曼编码处理后的byte[]数组
	 */
	public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
		// 1. 利用huffmanCodes  将原始bytes 转成赫夫曼编码后的字符串
		// 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
		StringBuilder stringBuilder = new StringBuilder();
		// 遍历bytes数组
		for (byte b : bytes) {
			stringBuilder.append(huffmanCodes.get(b));
		}
		// 将编码后的字符串转成byte数组
		// 统计返回字符串的长度
		int len;
		if (stringBuilder.length() % 8 == 0) {
			len = stringBuilder.length() / 8;
		} else {
			len = stringBuilder.length() / 8 + 1;
		}
		// 创建存储压缩后的byte数组
		byte[] huffmanCodeBytes = new byte[len];
		int index = 0;
		for (int i = 0; i < stringBuilder.length(); i += 8) { // 因为是每8位对应一个byte , 所有步长+8
			String strByte;
			if (i + 8 > stringBuilder.length()) { // 不够8位
				strByte = stringBuilder.substring(i);
			} else {
				strByte = stringBuilder.substring(i, i + 8);
			}
			// 将strByte 转成一个byte, 放入 huffmanCodeBytes
			huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
			index++;
		}
		return huffmanCodeBytes;
	}

	// 生成赫夫曼树对应的赫夫曼编码
	static HashMap<Byte, String> huffmanCodes = new HashMap<>();
	static StringBuilder stringBuilder = new StringBuilder();

	public static Map<Byte, String> getCodes(Node root) {
		if (root == null) {
			return null;
		}
		getCodes(root.left, "0", stringBuilder);
		getCodes(root.right, "1", stringBuilder);
		return huffmanCodes;
	}

	/**
	 * 思路
	 * 1. 将赫夫曼编码表放入Map<Byte,String>
	 * 32->101 , 97->100 100->11000 等等[形式]
	 * 2. 在生成赫夫曼编码表时, 需要去拼接路径 定义StringBuilder 存储某个叶子节点的路径
	 * 生成的赫夫曼编码表:{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
	 */
	/**
	 * 将传入的node节点的所有叶子节点的赫夫曼编码得到,  并放入HuffmanCodes集合中
	 *
	 * @param node          传入节点
	 * @param code          路径: 左子节点 表示 0 右子节点表示1
	 * @param stringBuilder 用于拼接路径
	 */
	private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
		StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
		// 将code加入到stringBuilder2
		stringBuilder2.append(code);
		if (node != null) { // node ==null 不处理
			// 判断当前节点时叶子节点还是非叶子节点
			if (node.data == null) {// 非叶子节点
				// 递归处理
				getCodes(node.left, "0", stringBuilder2);
				// 向右递归
				getCodes(node.right, "1", stringBuilder2);
			} else { // 说明找到是一个叶子节点
				huffmanCodes.put(node.data, String.valueOf(stringBuilder2));
			}
		}
	}

	/**
	 * @param bytes 接受一个字节数组
	 * @return 返回一个node 集合
	 */
	private static List<Node> getNodes(byte[] bytes) {
		List<Node> nodes = new ArrayList<>();

		// 存储每个byte 出现的次数
		Map<Byte, Integer> counts = new HashMap<>();
		for (byte b : bytes) {
			counts.merge(b, 1, Integer::sum);
		}
		// 把每个键值对封装成node对象,加入集合中
		for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
			nodes.add(new Node(entry.getKey(), entry.getValue()));
		}
		return nodes;
	}

	private static Node createHuffmanTree(List<Node> nodes) {
		while (nodes.size() > 1) {
			// 从小到大排
			Collections.sort(nodes);
			Node left = nodes.get(0);
			Node right = nodes.get(1);
			Node parent = new Node(null, left.weight + right.weight);
			parent.left = left;
			parent.right = right;
			nodes.remove(left);
			nodes.remove(right);
			nodes.add(parent);
		}
		// 返回赫夫曼树的根节点
		return nodes.get(0);
	}
}

// 创建node  带数据和权值
class Node implements Comparable<Node> {
	Byte data; // 存放数字(字符)本身, 比如 'a' =>97  ' ' =>32
	int weight; // 权值 表示字符出现的次数
	Node left;
	Node right;


	// 前序遍历
	public void preOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.preOrder();
		}

		if (this.right != null) {
			this.right.preOrder();
		}
	}

	public Node(Byte data, int weight) {
		this.data = data;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		return this.weight - o.weight;
	}

	@Override
	public String toString() {
		return "Node{" +
				"data=" + data +
				", weight=" + weight +
				'}';
	}
}